// 提交链接 https://leetcode.cn/problems/count-ways-to-build-good-strings/submissions/530231399/
// 2446. 统计构造好字符串的方案数
// 完成日期： 2024.9.8
// c++ 动态规划枚举划分区域，累加长度从low到high的方案数

class Solution {
public:
    int dp[100005];
    int countGoodStrings(int low, int high, int zero, int one) {
        dp[0] = 1;
        for (int i = 1; i <= high; i++)
        {
            int ans = 0;
            if (i >= zero) ans += dp[i - zero] % int(1e9 + 7);
            if (i >= one) ans += dp[i - one] % int(1e9 + 7);
            dp[i] = ans % int(1e9 + 7);
        }
        int ans = 0;
        for (int i = low; i <= high; i++)
        {
            ans += dp[i];
            ans %= int(1e9 + 7);
        }
        return ans;
    }
};